Beyond pages supporting efficient

DoCQS a prototype system for supporting data%2Doriented content query.

Data%2Doriented content query system searching for data into text on the web.

AIDE ad%2Dhoc intents detection engine over query logs.

Deep%2DWeb Search.
This paper presents a survey on the major approaches to search interface understanding. The Deep Web consists of data that exist on the Web but are inaccessible via text search engines. The traditional way to access these data, i.e., by manually filling-up HTML forms on search interfaces, is not scalable given the growing size of Deep Web. Automatic access to these data requires an automatic understanding of search interfaces. While it is easy for a human to perceive an interface, machine processing of an interface is challenging. During the last decade, several works addressed the automatic interface understanding problem while employing a variety of understanding strategies. This paper presents a survey
Integrating web query results holistic schema matching.

Probabilistic top%2Dk and ranking%2Daggregate queries.

Trustworthy keyword search for compliance storage.

Advances in Web and Network Technologies

Entity Search Engine Towards Agile Best%2DEffort Information Integration over the Web.

Collaborative Wrapping A Turbo Framework for Web Data Extraction.

Dewex An Exploration Facility for Enabling the Deep Web Integration.

Top%2Dk Query Processing in Uncertain Databases.
Top-k processing in uncertain databases is semantically and computationally different from traditional top-k processing. The interplay between score and uncertainty makes traditional techniques inapplicable. We introduce new probabilistic formulations for top-k queries. Our formulations are based on “marriage ” of traditional top-k semantics and possible worlds semantics. In the light of these formulations, we construct a framework that encapsulates a state space model and efficient query processing techniques to tackle the challenges of uncertain data settings. We prove that our techniques are optimal in terms of the number of accessed tuples and materialized search states. Our experiments show the efficiency of our techniques under different data distributions with orders of magnitude improvement over naïve materialization of possible worlds. 1
Progressive and selective merge computing top%2Dk with ad%2Dhoc ranking functions.
The family of threshold algorithm (i.e., TA) has been widely studied for efficiently computing top-k queries. TA uses a sort-merge framework that assumes data lists are pre-sorted, and the ranking functions are monotone. However, in many database applications, attribute values are indexed by treestructured indices (e.g., B-tree, R-tree), and the ranking functions are not necessarily monotone. To answer top-k queries with ad-hoc ranking functions, this paper studies an index-merge paradigm that performs progressive search over the space of joint states composed by multiple index nodes. We address two challenges for efficient query processing. First, to minimize the search complexity, we present a doubleheap algorithm which supports not only progressive state search but also progressive state generation. Second, to avoid unnecessary disk access, we characterize a type of “empty-state ” that does not contribute to the final results, and propose a new materialization model, join-signature, to prune empty-states. Our performance study shows that the proposed method achieves one order of magnitude speed-up over baseline solutions.
URank formulation and efficient evaluation of top%2Dk queries in uncertain databases.
Top-k processing in uncertain databases is semantically and computationally different from traditional top-k processing. The interplay between query scores and data uncertainty makes traditional techniques inapplicable. We introduce URank, a system that processes new probabilistic formulations of top-k queries in uncertain databases. The new formulations are based on marriage of traditional top-k semantics with possible worlds semantics. URank encapsulates a new processing framework that leverages existing query processing capabilities, and implements efficient search strategies that integrate ranking on scores with ranking on probabilities, to obtain meaningful answers for top-k queries.
Supporting entity search a large%2Dscale prototype search engine.

Supporting ranking and clustering as generalized order%2Dby and group%2Dby.
The Boolean semantics of SQL queries cannot adequately capture the “fuzzy ” preferences and “soft ” criteria required in non-traditional data retrieval applications. One way to solve this problem is to add a flavor of “information retrieval ” into database queries by allowing fuzzy query conditions and flexibly supporting grouping and ranking of the query results within the DBMS engine. While ranking is already supported by all major commercial DBMSs natively, support of flexibly grouping is still very limited (i.e., group-by). In this paper, we propose to generalize group-by to enable flexible grouping (clustering specifically) of the query results. Different from clustering in data mining applications, our focus is on supporting efficient clustering of Boolean results generated at query time. Moreover, we propose to integrate ranking and clustering with Boolean conditions, forming a new type of ClusterRank query to allow structured data retrieval. Such an integration is nontrivial in terms of both semantics and query processing. We investigate various semantics of this type of queries. To process such queries, a straightforward approach is to simply glue the techniques developed for ranking-only and clustering-only together. This approach is costly since both ranking and clustering are treated as blocking post-processing tasks upon Boolean query results by existing techniques. We propose a summary-based evaluation method that utilizes bitmap index to seamlessly integrate Boolean conditions, clustering, and ranking. Experimental study shows that our approach significantly outperforms the straightforward one and maintains high clustering quality.
EntityRank Searching Entities Directly and Holistically.
As the Web has evolved into a data-rich repository, with the standard “page view, ” current search engines are becoming increasingly inadequate for a wide range of query tasks. While we often search for various data “entities ” (e.g., phone number, paper PDF, date), today’s engines only take us indirectly to pages. While entities appear in many pages, current engines only find each page individually. Toward searching directly and holistically for finding information of finer granularity, we study the problem of entity search, a significant departure from traditional document retrieval. We focus on the core challenge of ranking entities, by distilling its underlying conceptual model Impression Model and developing a probabilistic ranking framework, EntityRank, that is able to seamlessly integrate both local and global information in ranking. We evaluate our online prototype over a 2TB Web corpus, and show that EntityRank performs effectively. 1.
Context%2DAware Wrapping Synchronized Data Extraction.
The deep Web presents a pressing need for integrating large numbers of dynamically evolving data sources. To be more automatic yet accurate in building an integration system, we observe two problems: First, across sequential tasks in integration, how can a wrapper (as an extraction task) consider the peer sources to facilitate the subsequent matching task? Second, across parallel sources, how can a wrapper leverage the peer wrappers or domain rules to enhance extraction accuracy? These issues, while seemingly unrelated, both boil down to the lack of “context awareness”: Current automatic wrapper induction approaches generate a wrapper for one source at a time, in isolation, and thus inherently lack the awareness of the peer sources or domain knowledge in the context of integration. We propose the concept of context-aware wrappers that are amenable to matching and that can leverage peer wrappers or prior domain knowledge. Such context awareness inspires a synchronization framework to construct wrappers consistently and collaboratively across their mutual context. We draw the insight from turbo codes and develop the turbo syncer to interconnect extraction with matching, which together achieve context awareness in wrapping. Our experiments show that the turbo syncer can, on the one hand, enhance extraction consistency and thus increase matching accuracy (from 17-83 % to 78-94 % in F-measure) and, on the other hand, incorporate peer wrappers and domain knowledge seamlessly to reduce extraction errors (from 09-60 % to 01-11%). 1.
Optimizing top%2Dk queries for middleware access A unified cost%2Dbased approach.
This paper studies optimizing top-k queries in middlewares. While many assorted algorithms have been proposed, none is generally applicable to a wide range of possible scenarios. Existing algorithms lack “generality” to support a wide range of access scenarios and systematic “adaptivity” to account for runtime specifics. To fulfill this critical lacking, we aim at taking a cost-based optimization approach: By runtime search over a space of algorithms, cost-based optimization is general across a wide range of access scenarios, yet adaptive to the specific access costs at runtime. While such optimization has been taken for granted for relational queries from early on, it has been clearly lacking for ranked queries. In this paper, we thus identify and address the barriers to realizing such a unified framework. As the first barrier, we need to define a “comprehensive” space encompassing all possibly optimal algorithms to search over. As the second barrier, as a conflicting goal, such a space should also be “focused ” enough to enable efficient search. For SQL queries that are explicitly composed of relational operators, such a space by definition consists of schedules of such operators (or “query plans”). In contrast, top-k queries have no such notion of logical tasks as a unit of scheduling. We thus define logical tasks of top-k queries as building blocks to identify a comprehensive and focused space for top-k queries. We then develop efficient search schemes over such space for identifying the optimal algorithm. Our study indicates that our framework not only unifies but also outperforms existing algorithms specifically designed for their scenarios.
Accessing the deep web.
The Web has been rapidly &#034;deepened&#034; by myriad  searchable databases online. To enable effective  access to the &#034;deep Web,&#034; we are building  the MetaQuerier-- for exploring and integrating  databases on the Web. Such metaquerying must  tackle integration at a large scale (as sources are  proliferating online) and of a dynamic nature (as  each query will access different sources). Toward  such integration, our approach hinges on the insight  that the challenge of large scale is itself an  opportunity: We observe that the desired &#034;semantics  &#034; often connects to surface presentation characteristics,  through some hidden regularities over  many sources. Generalizing our recent works, this  paper thus proposes our approach of shallow integration   across holistic sources -- to discover desired  semantics by exploiting the hidden regularities  of shallow clues across many sources holistically.
Probe Minimization by Schedule Optimization Supporting Top%2DK Queries with Expensive Predicates.
Abstract—This paper addresses the problem of evaluating ranked top-k queries with expensive predicates. As major DBMSs now all support expensive user-defined predicates for Boolean queries, we believe such support for ranked queries will be even more important: First, ranked queries often need to model user-specific concepts of preference, relevance, or similarity, which call for dynamic user-defined functions. Second, middleware systems must incorporate external predicates for integrating autonomous sources typically accessible only by per-object queries. Third, ranked queries often accompany Boolean ranking conditions, which may turn predicates into expensive ones, as the index structure on the predicate built on the base table may be no longer effective in retrieving the filtered objects in order. Fourth, fuzzy joins are inherently expensive, as they are essentially user-defined operations that dynamically associate multiple relations. These predicates, being dynamically defined or externally accessed, cannot rely on index mechanisms to provide zero-time sorted output, and must instead require per-object probe to evaluate. To enable probe minimization, we develop the problem as cost-based optimization of searching over potential probe schedules. In particular, we decouple probe scheduling into object and predicate scheduling problems and develop an analytical object scheduling optimization and a dynamic predicate scheduling optimization, which combined together form a cost-effective probe schedule. Index Terms—Database query processing, distributed information systems, database systems. 1
Enabling soft queries for data retrieval.

Boolean   ranking querying a database by k%2Dconstrained optimization.

Supporting ad%2Dhoc ranking aggregates.
This paper presents a principled framework for efficient processing of ad-hoc top-k (ranking) aggregate queries, which provide the k groups with the highest aggregates as results. Essential support of such queries is lacking in current systems, which process the queries in a naïve materialize-group-sort scheme that can be prohibitively inefficient. Our framework is based on three fundamental principles. The Upper-Bound Principle dictates the requirements of early pruning, and the Group-Ranking and Tuple-Ranking Principles dictate group-ordering and tuple-ordering requirements. They together guide the query processor toward a provably optimal tuple schedule for aggregate query processing. We propose a new execution framework to apply the principles and requirements. We address the challenges in realizing the framework and implementing new query operators, enabling efficient group-aware and rankaware query plans. The experimental study validates our framework by demonstrating orders of magnitude performance improvement in the new query plans, compared with the traditional plans. 1.
Accessing the web from search to integration.
We have witnessed the rapid growth of the World Wide Web – The Web has not only “broadened ” but also “deepened”: A 1999 survey [1] estimated a total of 800 million pages on the Web at that time. Nowadays, 19.2 billion Web pages as reported by the recent index of Yahoo.com, denoting at least 24 times increase in six years. Further, while this surface Web has linked billions of static HTML pages, an equally or even more significant amount of information is “hidden ” on the deep Web, behind the query forms of searchable databases. A July 2000 survey [2] estimated 96,000 “search sites ” and 550 billion content pages in this deep Web. A more recent study [3] in April 2004 estimated 330,000 deep Web sources with over 1.2 million query forms, reflecting a fast 3-7 times increase in 4 years. With the virtually unlimited amount of unstructured and structured
Automatic complex schema matching across Web query interfaces A correlation mining approach.
To enable information integration, schema matching is a critical step for discovering semantic correspondences of attributes across heterogeneous sources. While complex matchings are common, because of their far more complex search space, most existing techniques focus on simple 1:1 matchings. To tackle this challenge, this article takes a conceptually novel approach by viewing schema matching as correlation mining, for our task of matching Web query interfaces to integrate the myriad databases on the Internet. On this “deep Web, ” query interfaces generally form complex matchings between attribute groups (e.g., {author} corresponds to {first name, last name} in the Books domain). We observe that the co-occurrences patterns across query interfaces often reveal such complex semantic relationships: grouping attributes (e.g., {first name, last name}) tend to be co-present in query interfaces and thus positively correlated. In contrast, synonym attributes are negatively correlated because they rarely co-occur. This insight enables us to discover complex matchings by a correlation mining approach. In particular, we develop the DCM framework, which consists of data preprocessing, dual mining of positive and negative correlations, and finally matching construction. We evaluate the DCM framework on manually extracted interfaces and the results show good accuracy for discovering complex matchings. Further, to automate the
Toward Large Scale Integration Building a MetaQuerier over Databases on the Web.
The Web has been rapidly &#034;deepened&#034; by myriad  searchable databases online, where data are hidden  behind query interfaces. Toward large scale  integration over this &#034;deep Web,&#034; we have been  building the MetaQuerier system-- for both exploring  (to find) and integrating (to query) databases  on the Web. As an interim report, first,  this paper proposes our goal of the MetaQuerier  for Web-scale integration-- With its dynamic and  ad-hoc nature, such large scale integration mandates  both dynamic source discovery and on-thefly  query translation. Second, we present the  system architecture and underlying technology of  key subsystems in our ongoing implementation.
Towards Building a MetaQuerier Extracting and Matching Web Query Interfaces.
Introduction  Recently, we witness the rapid growth and thus the prevalence of databases on the Web. Our recent study [1] in April 2004 estimated 450,000 online databases. On this deep Web, myriad databases provide dynamic query-based data access through their query interfaces, instead of static URL links. It is thus essential to integrate these query interfaces for integrating the deep Web.  The overall goal of the MetaQuerier project (http://- metaquerier.cs.uiuc.edu) aims at opening up the deep Web to users, by building a system to help users exploring and integrating deep Web sources. In particular, to start with, we focus on the integration of deep Web sources in the same domain, which is itself an important integration task. The typical scenarios include purchasing a book with lowest price among book sources and a flight ticket with the best tradeoff between price and number of connections among airline sources. The deep Web presents challenges for such largescale  integration: W
Optimizing Access Cost for Top%2Dk Queries over Web Sources A Unified Cost%2Dbased Approach.
We study the problem of supporting ranked queries in middleware environments, where queries are evaluated over multiple sources. In particular, we study Web middleware scenarios, querying over various Web sources. To motivate, consider a Web “travel agent ” scenario for finding restaurants and hotels, as Examples 1 and 2 illustrate. (We use this real scenario as “benchmark ” queries for experiments as well.) In particular, how to access sources with different capabilities and costs, to answer queries efficiently? As our Web middleware coordinates various sources, each source access will incur network communication and server computation. This paper aims at optimizing such access costs– which dominate the overall query processing (like I/O in relational DBMS). Example 1: To find top- � restaurants (say, in the Chicago area) that are highly-rated and close to “myaddr, ” a user may ask a ranked query É (in SQL-like syntax): select name from Ö�×Ø�ÙÖ�ÒØ r order by Ñ�Ò Ö�Ø�Ò�(r.stars), ÐÓ×�(r.addr, myaddr) stop after 5 (Query É) For query answering, our middleware will access Web sources to evaluate the predicates, e.g., Ö�Ø�Ò�, intoscores in [0:1], which are then aggregated by some scoring function �, e.g.,  �  � Ñ�Ò, to return the highest-scored 5 restaurants. Our middleware can use various sources in query answering: Figure 1(a) shows one possible scenario: For evaluating ÐÓ×�: superpages.com is capable of 1) returning the ÐÓ× � score for a specific restaurant (“random access”) and 2) returning restaurants in their descending order of scores (“sorted access”). For Ö�Ø�Ò�: dineme.com similarly provides both sorted and random accesses. The middleware will coordinate these accesses to find the top results. Such accesses are typically expensive (as compared to local computations) with varying costs: To characterize, Figure 1(a) shows the average access latency (thus including both network and server times) of both
Enabling Ad%2Dhoc Ranking for Data Retrieval.
Data retrieval – finding relevant data from large databases – has become a serious problem. Consider user Amy, who is looking for a house in Chicago. She searches realtor.com with a few constraints on city, price range, beds, baths, which returns 3,581 matching houses. Or, Amy may realize that she must “narrow ” her query – However, on this extreme, and equally undesirable, she may as well get no hits at all. She will likely manually “oscillate” between these extremes, before eventually managing to complete her data retrieval task, if at all. Relational databases offer little support for such retrieval tasks. Traditional Boolean-based query models like SQL are based on “hard ” criteria (e.g., price ¢ $100,000) while users often employ “soft ” criteria for their specific senses of “relevance ” or “preference. ” Unlike flat Boolean results,
Making holistic schema matching robust an ensemble approach.

Making holistic schema matching robust an ensemble approach.

RankSQL Query Algebra and Optimization for Relational Top%2Dk Queries.
This paper introduces RankSQL, a system that provides a systematic and principled framework to support efficient evaluations of ranking (top-k) queries in relational database systems (RDBMS), by extending relational algebra and query optimization. Previously, top-k query processing is studied in the middleware scenario or in RDBMS in a “piecemeal ” fashion, i.e., focusing on specific operator or sitting outside the core of query engines. In contrast, we aim to support ranking as a first-class database construct. As a key insight, the new ranking relationship can be viewed as another logical property of data, parallel to the “membership ” property of relational data model. While membership is essentially supported in RDBMS, the same support for ranking is clearly lacking. We address the fundamental integration of ranking in RDBMS in a way similar to how membership, i.e., Boolean filtering, is supported. We extend relational algebra by proposing a rank-relational model to capture the ranking property, and introducing new and extended operators to support ranking as a first-class construct. Enabled by the extended algebra, we present a pipelined and incremental execution model of ranking query plans (that cannot be expressed traditionally) based on a fundamental ranking principle. To optimize top-k queries, we propose a dimensional enumeration algorithm to explore the extended plan space by enumerating plans along two dual dimensions: ranking and membership. We also propose a sampling-based method to estimate the cardinality of rank-aware operators, for costing plans. Our experiments show the validity of our framework and the accuracy of the proposed estimation model. 1.
RankSQL Query Algebra and Optimization for Relational Top%2Dk Queries.
This paper introduces RankSQL, a system that provides a systematic and principled framework to support efficient evaluations of ranking (top-k) queries in relational database systems (RDBMS), by extending relational algebra and query optimization. Previously, top-k query processing is studied in the middleware scenario or in RDBMS in a “piecemeal ” fashion, i.e., focusing on specific operator or sitting outside the core of query engines. In contrast, we aim to support ranking as a first-class database construct. As a key insight, the new ranking relationship can be viewed as another logical property of data, parallel to the “membership ” property of relational data model. While membership is essentially supported in RDBMS, the same support for ranking is clearly lacking. We address the fundamental integration of ranking in RDBMS in a way similar to how membership, i.e., Boolean filtering, is supported. We extend relational algebra by proposing a rank-relational model to capture the ranking property, and introducing new and extended operators to support ranking as a first-class construct. Enabled by the extended algebra, we present a pipelined and incremental execution model of ranking query plans (that cannot be expressed traditionally) based on a fundamental ranking principle. To optimize top-k queries, we propose a dimensional enumeration algorithm to explore the extended plan space by enumerating plans along two dual dimensions: ranking and membership. We also propose a sampling-based method to estimate the cardinality of rank-aware operators, for costing plans. Our experiments show the validity of our framework and the accuracy of the proposed estimation model. 1.
MetaQuerier querying structured web sources on%2Dthe%2Dfly.
Recently, we witness the rapid growth and thus the prevalence of databases on the Web. Our recent survey [2] in April 2004 estimated 450,000 online databases. On this deep Web, myriad online databases provide dynamic query-based data access through their
RankSQL Supporting Ranking Queries in Relational Database Management Systems.

Light%2Dweight Domain%2Dbased Form Assistant Querying Web Databases On the Fly.

Query Routing Finding Ways in the Maze of the DeepWeb.
This paper presents a source selection system based on attribute co-occurrence framework for ranking and selecting Deep Web sources that provide information relevant to users requirement. Given the huge number of heterogeneous Deep Web data sources, the end users may not know the sources that can satisfy their information needs. Selecting and ranking sources in relevance to the user requirements is challenging. Our system finds appropriate sources for such users by allowing them to input just an imprecise initial query. As a key insight, we observe that the semantics and relationships between deep Web sources are self-revealing through their query interfaces, and in essence, through the co-occurrences between attributes. Based on this insight, we design a co-occurrence based attribute graph for capturing the relevances of attributes, and using them in ranking of sources in the order of relevance to user’s requirement. Further, we present an iterative algorithm that realizes our model. Our preliminary evaluation on real-world sources demonstrates the effectiveness of our approach. 1.
Optimal multimodal fusion for multimedia data analysis.

Organizing structured web sources by query schemas a clustering approach.
In the recent years, the Web has been rapidly &#034;deepened&#034; with the prevalence of databases online. On this deep Web, many sources are structured by providing structured query interfaces and results. Organizing such structured sources into a domain hierarchy is one of the critical steps toward the integration of heterogeneous Web sources. We observe that, for structured Web sources, query schemas  (i.e., attributes in query interfaces) are discriminative representatives of the sources and thus can be exploited for source characterization. In particular, by viewing query schemas as a type of categorical data, we abstract the problem of source organization into the clustering of categorical data. Our approach hypothesizes that &#034;homogeneous sources&#034; are characterized by the same hidden generative models for their schemas. To find clusters governed by such statistical distributions, we propose a new objective function, model-differentiation, which employs principled hypothesis testing to maximize statistical heterogeneity among clusters. Our evaluation over hundreds of real sources indicates that (1) the schemabased clustering accurately organizes sources by object domains (e.g., Books, Movies), and (2) on clustering Web query schemas, the model-differentiation function outperforms existing ones, such as likelihood, entropy, and context linkages, with the hierarchical agglomerative clustering algorithm.
Mining complex matchings across Web query interfaces.

Clustering Structured Web Sources A Schema%2DBased
The Web has been rapidly &#034;deepened&#034; with the prevalence of databases online.
Discovering complex matchings across web query interfaces a correlation mining approach.
To enable information integration, schema matching is a critical step for discovering semantic correspondences of attributes across heterogeneous sources. While complex matchings are common, because of their far more complex search space, most existing techniques focus on simple 1:1 matchings. To tackle this challenge, this paper takes a conceptually novel approach by viewing schema matching as correlation mining, for our task of matching Web query interfaces to integrate the myriad databases on the Internet. On this &#034;deep Web,&#034; query interfaces generally form complex matchings  between attribute groups (e.g.,    corresponds to    name, last name} in the Books domain). We observe that the cooccurrences patterns across query interfaces often reveal such complex semantic relationships: grouping attributes (e.g.,    last name}) tend to be co-present in query interfaces and thus positively correlated. In contrast, synonym attributes are negatively correlated because they rarely co-occur. This insight enables us to discover complex matchings by a correlation mining approach. In particular, we develop the DCM framework, which consists of data preparation, dual mining of positive and negative correlations, and finally matching selection. Unlike previous correlation mining algorithms, which mainly focus on finding strong positive correlations, our algorithm cares both positive and negative correlations, especially the subtlety of negative correlations, due to its special importance in schema matching. This leads to the introduction of a new correlation measure, H-measure, distinct from those proposed in previous work. We evaluate our approach extensively and the results show good accuracy for discovering complex matchings.
Knocking the Door to the Deep Web Integration of Web Query Interfaces.
INTRODUCTION  Recently, we witness the rapid growth and thus the prevalence of databases on the Web. Our recent survey [2] in December 2002 estimated between 127,000 to 330,000 deep Web sources. On this deep Web, myriad online databases provide dynamic query-based data access through their query interfaces, instead of static URL links. As the &#034;door&#034; to the deep Web, it is essential to integrate these query interfaces for integrating the deep Web.  The overall goal of the MetaQuerier project (http://metaquerier.- cs.uiuc.edu) aims at opening up the deep Web to users, by building a system to help users exploring and integrating deep Web sources. In particular, to start with, we focus on the integration of deep Web sources in the same domain (e.g., Books, Airfares), which is itself an important integration task. The typical scenarios include purchasing a book with lowest price among book sources and a flight ticket with the best trade-off between price and number of connections among airl
Understanding Web Query Interfaces Best%2DEffort Parsing with Hidden Syntax.
Recently, the Web has been rapidly “deepened ” by many searchable databases online, where data are hidden behind query forms. For modelling and integrating Web databases, the very first challenge is to understand what a query interface says – or what query capabilities a source supports. Such automatic extraction of interface semantics is challenging, as query forms are created autonomously. Our approach builds on the observation that, across myriad sources, query forms seem to reveal some “concerted structure, ” by sharing common building blocks. Toward this insight, we hypothesize the existence of a hidden syntax that guides the creation of query interfaces, albeit from different sources. This hypothesis effectively transforms query interfaces into a visual language with a non-prescribed grammar – and, thus, their semantic understanding a parsing problem. Such a paradigm enables principled solutions for both declaratively representing common patterns, by a derived grammar, and systematically interpreting query forms, by a global parsing mechanism. To realize this paradigm, we must address the challenges of a hypothetical syntax – that it is to be derived, and that it is secondary to the input. At the heart of our form extractor, we thus develop a 2P grammar and a best-effort parser, which together realize a parsing mechanism for a hypothetical syntax. Our experiments show the promise of this approach – it achieves above 85 % accuracy for extracting query conditions across random sources. 1.
Knocking the Door to the Deep Web Integration of Web Query Interfaces.
INTRODUCTION  Recently, we witness the rapid growth and thus the prevalence of databases on the Web. Our recent survey [2] in December 2002 estimated between 127,000 to 330,000 deep Web sources. On this deep Web, myriad online databases provide dynamic query-based data access through their query interfaces, instead of static URL links. As the &#034;door&#034; to the deep Web, it is essential to integrate these query interfaces for integrating the deep Web.  The overall goal of the MetaQuerier project (http://metaquerier.- cs.uiuc.edu) aims at opening up the deep Web to users, by building a system to help users exploring and integrating deep Web sources. In particular, to start with, we focus on the integration of deep Web sources in the same domain (e.g., Books, Airfares), which is itself an important integration task. The typical scenarios include purchasing a book with lowest price among book sources and a flight ticket with the best trade-off between price and number of connections among airl
PEBL Web Page Classification without Negative Examples.
Web page classification is one of the essential techniques for Web mining because classifying Web pages of an interesting  class is often the first step of mining the Web. However, constructing a classifier for an interesting class requires laborious preprocessing  such as collecting positive and negative training examples. For instance, in order to construct a &#034;homepage&#034; classifier, one  needs to collect a sample of homepages (positive examples) and a sample of nonhomepages (negative examples). In particular,  collecting negative training examples requires arduous work and caution to avoid bias. This paper presents a framework, called  Positive Example Based Learning (PEBL), for Web page classification which eliminates the need for manually collecting negative  training examples in preprocessing. The PEBL framework applies an algorithm, called Mapping-Convergence (M-C), to achieve high  classification accuracy (with positive and unlabeled data) as high as that of a traditional SVM (with positive and negative data). M-C  runs in two stages: the mapping stage and convergence stage. In the mapping stage, the algorithm uses a weak classifier that draws  an initial approximation of &#034;strong&#034; negative data. Based on the initial approximation, the convergence stage iteratively runs an internal  classifier (e.g., SVM) which maximizes margins to progressively improve the approximation of negative data. Thus, the class boundary  eventually converges to the true boundary of the positive class in the feature space. We present the M-C algorithm with supporting  theoretical and experimental justifications. Our experiments show that, given the same set of positive examples, the M-C algorithm  outperforms one-class SVMs, and it is almost as accurate as the traditional SVMs.
Editorial special issue on web content mining.
With the phenomenal growth of the Web, there is an everincreasing volume of data and information published in numerous Web pages. The research in Web mining aims to develop new techniques to effectively extract and mine useful knowledge or
Mining semantics for large scale integration on the web evidences
The Web has been rapidly &#034;deepened&#034;-- with myriad searchable databases online, where data are hidden behind query interfaces. Toward large scale integration over this &#034;deep Web,&#034; we are facing a new challenge-- With its dynamic and ad-hoc nature, such large scale integration mandates dynamic semantics discovery. That is, we must on-the-fly cope with &#034;semantics&#034; of dynamically discovered sources without pre-configured source-specific knowledge. To tackle this challenge, our initial works hinge on the insight that the large scale is itself also a unique opportunity: We observe that the desired &#034;semantics&#034; often connects to surface presentation characteristics, through some hidden regularities over many sources. Such regularities can be essentially leveraged in enabling semantics discovery. In particular, we report our evidences in three initial tasks for integrating the deep Web: interface extraction, schema  matching, and query translation. Generalizing these specific evidences, we thus propose our &#034;unified insight&#034; of &#034;mining&#034; semantics for large scale integration by exploiting hidden regularities across holistic sources. Further, to fulfill the promise of such holistic mining, we discuss challenges toward its realization for dynamic semantics discovery. As our initial works as well as several related efforts have witnessed, we believe our unified insight, holistic mining for semantics discovery, is a promising methodology toward enabling large scale integration.
Structured Databases on the Web Observations and Implications.
The Web has been rapidly “deepened ” by the prevalence of databases online. With the potentially unlimited information hidden behind their query interfaces, this “deep Web ” of searchable databases is clearly an important frontier for data access. This paper surveys this relatively unexplored frontier, measuring characteristics pertinent to both exploring and integrating structured Web sources. On one hand, our “macro ” study surveys the deep Web at large, in April 2004, adopting the random IP-sampling approach, with one million samples. (How large is the deep Web? How is it covered by current directory services?) On the other hand, our “micro ” study surveys source-specific characteristics over 441 sources in eight representative domains, in December 2002. (How “hidden ” are deep-Web sources? How do search engines cover their data? How complex and expressive are query forms?) We report our observations and publish the resulting datasets to the research community. We conclude with several implications (of our own) which, while necessarily subjective, might help shape research directions and solutions. 1.
A Holistic Paradigm for Large Scale Schema Matching.
Schema matching is a critical problem for integrating heterogeneous information sources. Traditionally, the problem of matching multiple schemas has essentially relied on finding pairwise-attribute correspondences in isolation. In contrast, we propose a new matching paradigm, holistic schema matching, to match many schemas at the same time and find all matchings at once. By handling a set of schemas together, we can explore their context information that reflects the semantic correspondences among attributes. Such information is not available when schemas are matched only in pairs. As the realizations of holistic schema matching, we develop two alternative approaches: global evaluation and local evaluation. Global evaluation exhaustively assesses all possible &#034;models,&#034; where a model expresses all attribute matchings. In particular, we propose the MGS framework for such global evaluation, building upon the hypothesis of the existence of a hidden schema model that probabilistically generates the schemas we observed. On the other hand, local evaluation independently assesses every single matching to incrementally construct such a model. In particular, we develop the DCM framework for local evaluation, building upon the observation that co-occurrence patterns across schemas often reveal the complex relationships of attributes. We apply our approaches to match query interfaces on the deep Web. The result shows the effectiveness of both the MGS and DCM approaches, which together demonstrate the promise of holistic schema matching.
Statistical Schema Matching across Web Query Interfaces.
Schema matching is a critical problem for integrating heterogeneous information sources. Traditionally, the problem of matching multiple schemas has essentially relied on finding pairwise-attribute correspondence. This paper proposes a di#erent approach, motivated by integrating large numbers of data sources on the Internet. On this &#034;deep Web,&#034; we observe two distinguishing characteristics that o#er a new view for considering schema matching: First, as the Web scales, there are ample sources that provide structured information in the same domains (e.g., books and automobiles). Second, while sources proliferate, their aggregate schema vocabulary tends to converge at a relatively small size. Motivated by these observations, we propose a new paradigm, statistical schema matching : Unlike traditional approaches using pairwise-attribute correspondence, we take a holistic approach to match all input schemas by finding an underlying generative schema model. We propose a general statistical framework MGS for such hidden model discovery, which consists of hypothesis modeling, generation, and selection. Further, we specialize the general framework to develop Algorithm  MGSsd , targeting at synonym discovery, a canonical problem of schema matching, by designing and discovering a model that specifically captures synonym attributes. We demonstrate our approach over hundreds of real Web sources in four domains and the results show good accuracy.
Heterogeneous Learner for Web Page Classification.
Classification of an interesting class of Web pages (e.g., personal homepages, resume pages) has been an interesting problem. Typical machine learning algorithms for this problem require two classes of data for training: positive and negative training examples. However, in application to Web page classification, gathering an unbiased sample of negative examples appears to be difficult. We propose a heterogeneous learning framework for classifying Web pages, which (1) eliminates the need for negative training data, and (2) increases classification accuracy by using two heterogeneous learners. Our framework uses two heterogeneous learners -- a decision list and a linear separator which complement each other -- to eliminate the need for negative training data in the training phase and to increase the accuracy in the testing phase. Our results show that our heterogeneous framework achieves high accuracy without requiring negative training data; it enhances the accuracy of linear separators by reducing the errors on &#034;low-margin data&#034;. That is, it classifies more accurately while requiring less human efforts in training.
PEBL positive example based learning for Web page classification using SVM.
for Web mining. Specifically, classifying Web pages of a user-interesting class is the first step of mining interesting information from the Web. However, constructing a classifier for an interesting class requires laborious pre-processing such as collecting positive and negative training examples. For instance, in order to construct a &#034;homepage&#034; classifier, one needs to collect a sample of homepages (positive examples) and a sample of non-homepages (negative examples). In particular, collecting negative training examples requires arduous work and special caution to avoid biasing them. We introduce in this paper the Positive Example Based Learn- ing (PEBL) framework for Web page classification which eliminates the need for manually collecting negative training examples in pre-processing. We present an algorithm called Mapping-Convergence (M-C) that achieves classification accuracy (with positive and unlabeled data) as high as that of traditional SVM (with positive and negative data). Our experiments show that when the M-C algorithm uses the same amount of positive examples as that of traditional SVM, the M-C algorithm performs as well as traditional SVM.
Minimal probing supporting expensive predicates for top%2Dk queries.
This paper addresses the problem of evaluating ranked top-    queries with expensive predicates. As major DBMSs now all support expensive user-defined predicates for Boolean queries, we believe such support for ranked queries will be even more important: First, ranked queries often need to model user-specific concepts of preference, relevance, or similarity, which call for dynamic user-defined functions. Second, middleware systems must incorporate external predicates for integrating autonomous sources typically accessible only by per-object queries. Third, fuzzy joins are inherently expensive, as they are essentially user-defined operations that dynamically associate multiple relations. These predicates, being dynamically defined or externally accessed, cannot rely on index mechanisms to provide zero-time sorted output, and must instead require per-object probe to evaluate. The current standard sort-merge framework for ranked queries cannot efficiently handle such predicates because it must completely probe all objects, before sorting and merging them to produce top-    answers. To minimize expensive probes, we thus develop the formal principle of &#034;necessary probes,&#034; which determines if a probe is absolutely required. We then propose Algorithm MPro which, by implementing the principle, is provably optimal with minimal probe cost. Further, we show that MPro can scale well and can be easily parallelized. Our experiments using both a real-estate benchmark database and synthetic datasets show that MPro enables significant probe reduction, which can be orders of magnitude faster than the standard scheme using complete probing.
Data Mining for Web Intelligence.
Data mining holds the key to uncovering and...
Database Research at the University of Illinois at Urbana%2DChampaign.

NBDL a CIS framework for NSDL.
In this paper, we describe the NBDL (National Biology Digital Library) project, one of the six CIS (Core Integration System) projects of the NSF NSDL (National SMETE Digital Library) Program.
Approximate Query Translation Across Heterogeneous Information Sources.
In this paper we present a mechanism for  approximately translating Boolean query constraints  across heterogeneous information sources.  Achieving the best translation is challenging because  sources support different constraints for formulating  queries, and often these constraints cannot  be precisely translated. For instance, a query  [score ? 8] might be &#034;perfectly&#034; translated as  [rating ? 0.8] at some site, but can only be approximated  as [grade = A] at another. Unlike  other work, our general framework adopts a customizable  &#034;closeness&#034; metric for the translation  that combines both precision and recall. Our results  show that for query translation we need to  handle interdependencies among both query conjuncts  as well as disjuncts. As the basis, we identify  the essential requirements of a rule system for  users to encode the mappings for atomic semantic  units. Our algorithm then translates complex  queries by rewriting them in terms of the semantic  units. We show that, un...
Approximate query mapping Accounting for translation closeness.
In this paper we present a mechanism for approximately translating Boolean query constraints across heterogeneous information sources. Achieving the best translation is challenging because sources support different constraints for formulating queries, and often these constraints cannot be precisely translated. For instance, a query [score &gt; 8] might be &#034;perfectly&#034; translated as [rating &gt; 0.8] at some site, but can only be approximated as [grade = A] at another. Unlike other work, our general framework adopts a customizable &#034;closeness&#034; metric for the translation that combines both precision and recall. Our results show that for query translation we need to handle interdependencies among both query conjuncts as well as disjuncts. As the basis, we identify the essential requirements of a rule system for users to encode the mappings for atomic semantic units. Our algorithm then translates complex queries by rewriting them in terms of the semantic units. We show that, under practical assumptions, our algorithm generates the best approximate translations with respect to the closeness metric of choice. We also present a case study to show how our technique may be applied in practice.
Approximate Query Translation Across Heterogeneous Information Sources.
In this paper we present a mechanism for  approximately translating Boolean query constraints  across heterogeneous information sources.  Achieving the best translation is challenging because  sources support different constraints for formulating  queries, and often these constraints cannot  be precisely translated. For instance, a query  [score ? 8] might be &#034;perfectly&#034; translated as  [rating ? 0.8] at some site, but can only be approximated  as [grade = A] at another. Unlike  other work, our general framework adopts a customizable  &#034;closeness&#034; metric for the translation  that combines both precision and recall. Our results  show that for query translation we need to  handle interdependencies among both query conjuncts  as well as disjuncts. As the basis, we identify  the essential requirements of a rule system for  users to encode the mappings for atomic semantic  units. Our algorithm then translates complex  queries by rewriting them in terms of the semantic  units. We show that, un...
Mind Your Vocabulary Query Mapping Across Heterogeneous Information Sources.
In this paper we present a mechanism for translating constraint queries, i.e., Boolean expressions of  constraints, across heterogeneous information sources. Integrating such systems is difficult in part because  they use a wide range of constraints as the vocabulary for formulating queries. We describe algorithms  that apply user-provided mapping rules to translate query constraints into ones that are understood and  supported in another context, e.g., that use the proper operators and value formats. We show that the  translated queries minimally subsume the original ones. Furthermore, the translated queries are also  the most compact possible. Unlike other query mapping work, we effectively consider inter-dependencies  among constraints, i.e., we handle constraints that cannot be translated independently. Furthermore,  when constraints are not fully supported, our framework explores relaxations (semantic rewritings) into  the closest supported version. Our most sophisticated algorith...
PowerBookmarks A System for Personalizable Web Information Organization
Users of the Web are overloaded with information. This medium is “polluted ” with redundant, erroneous and low quality information. A WWW survey of 11,700 users conducted from April 10 to May 10, 1996[1] indicates that 30.31 % of the users report “finding known info ” is their problem and 27.80 % of the users report organizing collected information as their problem. An empirical study[2] on users ’ revisitation patterns to WWW pages found that 58 % of an individual’s pages are revisits. With these study results, we believe the Web users would like to build and organize a larger collection of bookmarks for future references than they can reasonably maintain now. 2. System Architecture PowerBookmarks is being developed under the auspices of a larger WebDB project to address the above issues. WebDB hypermedia database system[3] is built on top of NEC PERCIO Object-Oriented Database Manage-ment System[4]. Unlike most search engines, which fo-
Predicate Rewriting for Translating Boolean Queries in a Heterogeneous Information System.
Usually referred to as fielded search, a predicate specifies a pattern to be matched against the content of a field (Figure 2 , Construct 2). Typically, for each searchable field, IR systems build indexes [Salton 1989; Frakes and Baeza-Yates 1992; Faloutsos 1985] to direct the search engine to find documents with some given term, such as the word cat or phrase &#034;Joe Doe&#034;. The indexing schemes of a field restrict how it can be queried. Generally, there are two ways of indexing    .
Using Distributed Objects to Build the Stanford Digital Library Infobus.

An Extensible Constructor Tool for the Rapid
We describe an extensible constructor tool that helps information experts (e.g., librarians) create specialized query synthesizers for heterogeneous digital-library environments. A query synthesizer provides a graphical user interface in which a digital-library patron can specify a high-level, fielded, multi-source query. Furthermore, a query synthesizer interacts with a query translator and an attribute translator to transform high-level queries into sets of source-specific queries. We discuss how the constructor can facilitate discovery of available attributes (e.g., title), collation of schemas from different sources, selection of input widgets for a synthesizer (e.g., a text box or a drop-down list widget to support input of controlled vocabulary),, and other design aspects. We also describe a prototype constructor we implemented, based on the Stanford InfoBus and metadata architecture.  KEYWORDS: constructor tool, query synthesizer, regional schema, query generation, query transla...
Conjunctive Constraint Mapping for Data Translation.
In this paper we present a mechanism for translating information in heterogeneous digital library environments. We model information as a set of conjunctive constraints that are satisfied by real-world objects (e.g., documents, their metadata) . Through application of semantic rules and value transformation functions, constraints are mapped into ones understood and supported in another context. Our machinery can also deal with hierarchically structured information.  KEYWORDS: constraint mapping, data translation, semantic interoperability.  1 INTRODUCTION  Digital libraries often need to interact with autonomous systems that structure and represent their information differently. To ensure semantic interoperability [12], information must be appropriately mapped from its source context to its target context where it will be used. For example, the condition [author = &#034;John Smith&#034;] in a query, may need to be translated to [name = &#034;Smith, J.&#034;]. Similarly, the component [date = &#034;Jan 1998&#034;] i...
PowerBookmarks An Advanced Web Bookmark Database System and its Information Sharing and Management.

The Stanford InfoBus and Its Service Layers Augmenting the Internet with High%2DLevel Information Management Protocols.

Interoperability for Digital Libraries Worldwide.

Evaluating the Cost of Boolean Query Mapping.
Non-uniform query languages make searching over heterogeneous information sources difficult. Our approach is to allow a user to compose Boolean queries in one rich front-end language. For each user query and target source, we transform the user query into a subsuming query that can be supported by the source but that may return extra documents. The results are then processed by a filter query to yield the correct final results. This post-filtering approach may involve significant cost because the documents that the users will not see may have to be retrieved and filtered. There are generally two ways to implement post-filtering: batch post-filtering and incremental post-filtering. In this paper we evaluate the costs of both methods for different search features such as proximity operators. The experimental results show that in many cases incremental post-filtering cost may be acceptable, while the batch post-filtering cost may sometimes be extremely large. 1 Introduction Emerging Digi...
Evaluating the Cost of Boolean Query Mapping.
Non-uniform query languages make searching over heterogeneous information sources difficult. Our approach is to allow a user to compose Boolean queries in one rich front-end language. For each user query and target source, we transform the user query into a subsuming query that can be supported by the source but that may return extra documents. The results are then processed by a filter query to yield the correct final results. This post-filtering approach may involve significant cost because the documents that the users will not see may have to be retrieved and filtered. There are generally two ways to implement post-filtering: batch post-filtering and incremental post-filtering. In this paper we evaluate the costs of both methods for different search features such as proximity operators. The experimental results show that in many cases incremental post-filtering cost may be acceptable, while the batch post-filtering cost may sometimes be extremely large. 1 Introduction Emerging Digi...
Metadata for Digital Libraries Architecture and Design Rationale.
In a distributed, heterogeneous, proxy-based digital library, autonomous services and collections are accessed indirectly via proxies. To facilitate metadata compatibility and interoperability in such a digital library, we have designed a metadata architecture that includes four basic component classes: attribute model proxies, attribute model translators, metadata facilities for search proxies, and metadata repositories. Attribute model proxies elevate both attribute sets and the attributes they define to first-class objects. They also allow relationships among attributes to be captured. Attribute model translators map attributes and attribute values from one attribute model to another (where possible) . Metadata facilities for search proxies provide structured descriptions both of the collections to which the search proxies provide access and of the search capabilities of the proxies. Finally, metadata repositories accumulate selected metadata from local instances of the other three ...
STARTS Stanford Proposal for Internet Meta%2DSearching %28Experience Paper%29.

The Stanford Digital Library Metadata Architecture.
. The overall goal of the Stanford Digital Library project is to provide an infrastructure that affords interoperability among heterogeneous, autonomous digital library services. These services include both search services and remotely usable information processing facilities. In this paper, we survey and categorize the metadata required for a diverse set of Stanford Digital Library services that we have built. We then propose an extensible metadata architecture that meets these requirements. Our metadata architecture fits into our established infrastructure and promotes interoperability among existing and de-facto metadata standards. Several pieces of this architecture are implemented; others are under construction. The architecture includes attribute model proxies, attribute model translation services, metadata information facilities for search services, and local metadata repositories. In presenting and discussing the pieces of the architecture, we show how they address our motivati...
Boolean Query Mapping Across Heterogeneous Information Sources.
Searching over heterogeneous information sources is difficult because of the non-uniform query languages. Our approach is to allow a user to compose Boolean queries in one rich front-end language. For each user query and target source, we transform the user query into a subsuming query that can be supported by the source but that may return extra documents. The results are then processed by a filter query to yield the correct final result. In this paper we introduce the architecture and associated algorithms for generating the supported subsuming queries and filters. We show that generated subsuming queries return a minimal number of documents; we also discuss how minimal cost filters can be obtained. We have implemented prototype versions of these algorithms and demonstrated them on heterogeneous Boolean systems. Index Terms Boolean queries, query translation, information retrieval, heterogeneity, digital libraries, query subsumption, filtering. I. Introduction  Emerging Digital Libra...
